数据结构Java实现07

您所在的位置：网站首页 › front等于rear 元素个数 › 数据结构Java实现07

数据结构Java实现07

2023-08-24 08:32| 来源: 网络整理| 查看: 265

一、队列的概念：

　　队列（简称作队，Queue）也是一种特殊的线性表，队列的数据元素以及数据元素间的逻辑关系和线性表完全相同，其差别是线性表允许在任意位置插入和删除，而队列只允许在其一端进行插入操作在其另一端进行删除操作。

队列中允许进行插入操作的一端称为队尾，允许进行删除操作的一端称为队头。队列的插入操作通常称作入队列，队列的删除操作通常称作出队列。

下图是一个依次向队列中插入数据元素a0,a1,...,an-1后的示意图：

faf7d1e6-07b1-44bb-9752-5fcc113a0648

上图中，a0是当前队头数据元素，an-1是当前队尾数据元素。

为了避免当只有一个元素时，对头和队尾重合使得处理变得麻烦，所以引入两个指针：front指针指向队头元素，rear指针指向队尾元素的下一个位置，这样的话，当front指针等于rear时，此队列不是还剩一个元素，而是空队列。

二、队列的抽象数据类型：

数据集合：

　　队列的数据集合可以表示为a0,a1,…,an-1，每个数据元素的数据类型可以是任意的类型。

操作集合：

（1）入队列append(obj)：把数据元素obj插入队尾。

（2）出队列delete()：把队头数据元素删除并由函数返回。

（3）取队头数据元素getFront()：取队头数据元素并由函数返回。

（4）非空否isEmpty()：非空否。若队列非空，则函数返回false，否则函数返回true。

三、循环顺序队列：

线性表有顺序存储和链式存储，队列是一种特殊的线性表，同样也存在这两种存储方式。我们先来看一下队列的顺序存储。

1、顺序队列的“假溢出”：

607ede1a-91b5-4ac9-8850-07078379fddb

上图中，front指针指向队头元素，rear指针指向队尾元素的下一个位置。图(d)中b、c、d出队后，front指针指向元素e，rear指针在数组外面。假设这个队列的总个数不超过5个，但目前如果接着入队的话，因数组末尾元素已经被占用，再向后加就会产生数组越界的错误，可实际上队列在下标为0、1、2、3、4的地方还是空闲的，我们把这种现象叫做“假溢出”。

2、循环顺序队列：

所以解决假溢出的办法就是后面满了，就再从头开始，也就是头尾相接的循环。我们把队列的这种逻辑上首尾相连的顺序存储结构称为循环队列。

如何判断循环队列究竟是空的还是满的：

　　现在问题又来了，我们之前说，空队列时，front指针等于rear指针，那么现在循环队列满的时候，也是front等于rear，那么如何判断循环队列究竟是空的还是满的？有如下办法：

办法1：设置一个标志位flag。初始时置flag=0；每当入队列操作成功就置flag=1；每当出队列操作成功就置flag=0。则队列空的判断条件为：rear == front && tag==0；队列满的判断条件为：rear = = front && tag= =1。办法2：保留一个元素的存储空间。此时，队列满时的判断条件为 (rear + 1) % maxSize == front；队列空的判断条件还是front == rear。办法3：设计一个计数器count，统计队列中的元素个数。此时，队列满的判断条件为：count > 0 && rear == front ；队列空的判断条件为count == 0。

我们在接下来的代码中采用方法3来实现。

3、代码实现：(循环顺序队列的创建)

(1)Queue.java:(队列接口)

1 //队列接口 2 public interface Queue { 3 4 //入队 5 public void append(Object obj) throws Exception; 6 7 //出队 8 public Object delete() throws Exception; 9 10 //获得队头元素 11 public Object getFront() throws Exception; 12 13 //判断对列是否为空 14 public boolean isEmpty(); 15 }

(2)CircleSequenceQueue.java:（循环顺序队列）

1 //循环顺序队列 2 public class CircleSequenceQueue implements Queue { 3 4 static final int defaultSize = 10; //默认队列的长度 5 int front; //队头 6 int rear; //队尾 7 int count; //统计元素个数的计数器 8 int maxSize; //队的最大长度 9 Object[] queue; //队列 10 11 public CircleSequenceQueue() { 12 init(defaultSize); 13 } 14 15 public CircleSequenceQueue(int size) { 16 init(size); 17 } 18 19 public void init(int size) { 20 maxSize = size; 21 front = rear = 0; 22 count = 0; 23 queue = new Object[size]; 24 } 25 26 @Override 27 public void append(Object obj) throws Exception { 28 // TODO Auto-generated method stub 29 if (count > 0 && front == rear) { 30 throw new Exception("队列已满！"); 31 } 32 queue[rear] = obj; 33 rear = (rear + 1) % maxSize; 34 count++; 35 } 36 37 @Override 38 public Object delete() throws Exception { 39 // TODO Auto-generated method stub 40 if (isEmpty()) { 41 throw new Exception("队列为空！"); 42 } 43 Object obj = queue[front]; 44 front = (front + 1) % maxSize; 45 count--; 46 return obj; 47 } 48 49 @Override 50 public Object getFront() throws Exception { 51 // TODO Auto-generated method stub 52 if (!isEmpty()) { 53 return queue[front]; 54 } else { 55 return null; 56 } 57 } 58 59 @Override 60 public boolean isEmpty() { 61 // TODO Auto-generated method stub 62 return count == 0; 63 } 64 65 }

(3)Test.java:

1 public class Test { 2 public static void main(String[] args) throws Exception { 3 4 CircleSequenceQueue queue = new CircleSequenceQueue(); 5 queue.append("a"); 6 queue.append("b"); 7 queue.append("c"); 8 queue.append("d"); 9 queue.append("e"); 10 queue.append("f"); 11 12 queue.delete(); 13 queue.delete(); 14 15 queue.append("g"); 16 17 while (!queue.isEmpty()) { 18 System.out.println(queue.delete()); 19 } 20 } 21 }

运行效果：

251fa2d6-120f-4b20-8754-f7a795b20cf1

4、循环队列应用：

　　使用顺序循环队列和多线程实现一个排队买票的例子。而且，我们只允许这个队伍中同时排队的只有10个人，那就需要用到队列了。

　　　　生产者（等候买票）

　　　　消费者 (买票离开)

这里面我们需要用到上面的Queue.java类和CircleSequenceQueue.java类。

代码结构：

62c99e55-fe55-41d0-8794-7a74a37ca826

(3)WindowQueue.java:

1 //卖票窗口 2 public class WindowQueue { 3 4 //卖票的队列 5 int maxSize = 10; 6 CircleSequenceQueue queue = new CircleSequenceQueue(maxSize); 7 int num = 0; //统计卖票的数量，一天最多卖100张票。 8 boolean isAlive = true; //判断是否继续卖票。 9 10 //排队买票 11 public synchronized void producer() throws Exception { 12 if (queue.count 0) { 29 Object obj = queue.delete(); 30 int temp = Integer.parseInt(obj.toString()); 31 System.out.println("第" + (temp + 1) + "个客户买到票离开队列！"); 32 //如果当前队列为空，并且卖出票的数量大于等于100，说明卖票结束 33 if (queue.isEmpty() && this.num >= 100) { 34 this.isAlive = false; 35 } 36 this.notifyAll(); //唤醒排队买票的线程。 37 } else { 38 try { 39 System.out.println("队列已空...请等待！"); 40 this.wait();//队列空时，卖票线程等待。 41 } catch (Exception ex) { 42 ex.printStackTrace(); 43 } 44 } 45 } 46 }

(4)Producer.java:

1 //买票者 2 public class Producer implements Runnable { 3 4 WindowQueue queue; 5 6 public Producer(WindowQueue queue) { 7 this.queue = queue; 8 } 9 10 @Override 11 public void run() { 12 // TODO Auto-generated method stub 13 while (queue.num < 100) { 14 try { 15 queue.producer(); 16 } catch (Exception ex) { 17 ex.printStackTrace(); 18 } 19 } 20 } 21 22 }

(5)Consumer.java:

//卖票者 public class Consumer implements Runnable { WindowQueue queue; public Consumer(WindowQueue queue) { this.queue = queue; } @Override public void run() { // TODO Auto-generated method stub while (queue.isAlive) { try { queue.consumer(); } catch (Exception ex) { ex.printStackTrace(); } } } }

(6)test.java:

1 public class Test { 2 3 public static void main(String[] args) throws Exception { 4 5 WindowQueue queue = new WindowQueue(); 6 7 Producer p = new Producer(queue);//注意一定要传同一个窗口对象 8 Consumer c = new Consumer(queue); 9 10 //排队买票线程 11 Thread pThread = new Thread(p); 12 //卖票线程 13 Thread cThread = new Thread(c); 14 15 pThread.start(); //开始排队买票 16 cThread.start(); //开始卖票 17 } 18 19 }

注意第07行的注释。

运行效果：

bb9b709e-bc10-48ab-89e6-260ca38ae5d2

四、链式队列：

链式队列其实就是特殊的单链表，只不过它只能尾进头出而已。链式队列的存储结构如下图所示：

6c1486eb-a189-413f-bce1-a8f516aede26

1、链式队列的实现：

(1)Node.java:结点类

1 //结点类 2 public class Node { 3 4 Object element; //数据域 5 Node next; //指针域 6 7 //头结点的构造方法 8 public Node(Node nextval) { 9 this.next = nextval; 10 } 11 12 //非头结点的构造方法 13 public Node(Object obj, Node nextval) { 14 this.element = obj; 15 this.next = nextval; 16 } 17 18 //获得当前结点的后继结点 19 public Node getNext() { 20 return this.next; 21 } 22 23 //获得当前的数据域的值 24 public Object getElement() { 25 return this.element; 26 } 27 28 //设置当前结点的指针域 29 public void setNext(Node nextval) { 30 this.next = nextval; 31 } 32 33 //设置当前结点的数据域 34 public void setElement(Object obj) { 35 this.element = obj; 36 } 37 38 public String toString() { 39 return this.element.toString(); 40 } 41 }

(2)Queue.java:

(3)LinkQueue.java:

1 public class LinkQueue implements Queue { 2 3 Node front; //队头 4 Node rear; //队尾 5 int count; //计数器 6 7 public LinkQueue() { 8 init(); 9 } 10 11 public void init() { 12 front = rear = null; 13 count = 0; 14 } 15 16 @Override 17 public void append(Object obj) throws Exception { 18 // TODO Auto-generated method stub 19 Node node = new Node(obj, null); 20 21 //如果当前队列不为空。 22 if (rear != null) { 23 rear.next = node; //队尾结点指向新结点 24 } 25 26 rear = node; //设置队尾结点为新结点 27 28 //说明要插入的结点是队列的第一个结点 29 if (front == null) { 30 front = node; 31 } 32 count++; 33 } 34 35 @Override 36 public Object delete() throws Exception { 37 // TODO Auto-generated method stub 38 if (isEmpty()) { 39 new Exception("队列已空！"); 40 } 41 Node node = front; 42 front = front.next; 43 count--; 44 return node.getElement(); 45 } 46 47 @Override 48 public Object getFront() throws Exception { 49 // TODO Auto-generated method stub 50 if (!isEmpty()) { 51 return front.getElement(); 52 } else { 53 return null; 54 } 55 } 56 57 @Override 58 public boolean isEmpty() { 59 // TODO Auto-generated method stub 60 return count == 0; 61 } 62 63 }

(4)Test.java:

1 public class Test { 2 3 public static void main(String[] args) throws Exception { 4 5 LinkQueue queue = new LinkQueue(); 6 queue.append("a"); 7 queue.append("b"); 8 queue.append("c"); 9 queue.append("d"); 10 queue.append("e"); 11 queue.append("f"); 12 13 queue.delete(); 14 queue.delete(); 15 16 queue.append("g"); 17 18 while (!queue.isEmpty()) { 19 System.out.println(queue.delete()); 20 } 21 } 22 }

运行效果：

7ee743ea-3e2a-4795-b7b3-10dfef4f3e9b

2、链式队列的应用：

题目：

　　编写一个判断一个字符串是否是回文的算法。

思路：

　　设字符数组str中存放了要判断的字符串。把字符数组中的字符逐个分别存入一个队列和栈中，然后逐个出队和出栈比较出队的字符与出栈的字符是否相同，若全部相等则该字符串为回文。

代码实现：

　　这里面需要用到上面一段中的LinkQueue类。代码结构如下：

3a04b30d-6ed1-4556-a408-afc8b4c6068a

(4)Stack.java:栈接口

1 //栈接口 2 public interface Stack { 3 4 //入栈 5 public void push(Object obj) throws Exception; 6 7 //出栈 8 public Object pop() throws Exception; 9 10 //获得栈顶元素 11 public Object getTop() throws Exception; 12 13 //判断栈是否为空 14 public boolean isEmpty(); 15 }

(5)LinkStack.java:

1 public class LinkStack implements Stack { 2 3 Node head; //栈顶指针 4 int size; //结点的个数 5 6 public LinkStack() { 7 head = null; 8 size = 0; 9 } 10 11 @Override 12 public Object getTop() throws Exception { 13 // TODO Auto-generated method stub 14 return head.getElement(); 15 } 16 17 @Override 18 public boolean isEmpty() { 19 // TODO Auto-generated method stub 20 return head == null; 21 } 22 23 @Override 24 public Object pop() throws Exception { 25 // TODO Auto-generated method stub 26 if (isEmpty()) { 27 throw new Exception("栈为空！"); 28 } 29 Object obj = head.getElement(); 30 head = head.getNext(); 31 size--; 32 return obj; 33 34 } 35 36 @Override 37 public void push(Object obj) throws Exception { 38 // TODO Auto-generated method stub 39 head = new Node(obj, head); 40 size++; 41 } 42 43 }

(6)Test.java:测试类

1 public class Test { 2 3 public static void main(String[] args) throws Exception { 4 5 String str1 = "ABCDCBA"; //是回文 6 String str2 = "ABCDECAB"; //不是回文 7 8 try { 9 if (Test.isHuiWen(str1)) { 10 System.out.println(str2 + ":是回文！"); 11 } else { 12 System.out.println(str2 + ":不是回文！"); 13 } 14 } catch (Exception ex) { 15 ex.printStackTrace(); 16 } 17 } 18 19 20 //方法：判断字符串是否回文 21 public static boolean isHuiWen(String str) throws Exception { 22 int n = str.length(); 23 LinkStack stack = new LinkStack();//创建堆栈 24 LinkQueue queue = new LinkQueue();//创建队列 25 for (int i = 0; i < n; i++) { 26 stack.push(str.subSequence(i, i + 1)); //把字符串每个字符压进堆栈 27 queue.append(str.subSequence(i, i + 1));//把字符串每个字符压入队列 28 } 29 while (!queue.isEmpty() && !stack.isEmpty()) { 30 if (!queue.delete().equals(stack.pop())) { //出队列，出栈，同时判断是否相同 31 return false; 32 } 33 } 34 35 return true; 36 } 37 38 }

3、循环队列和链式队列的比较：

（1）从时间上看，它们的基本操作都是常数时间，即O(1)的。不过循环队列是事先申请好空间，使用期间不释放；而链式队列，每次申请和释放结点也会存在一定的时间开销，如果入栈和出栈比较频繁，则两者还是有细微的差别。

（2）从空间上看，循环队列必须有一个固定的长度，所以就有了存储元素个数和空间浪费的问题。而链式队列不存在这个问题，尽管它需要一个指针域，会产生一些空间上的开销，但也可以接受。所以在空间上，链式队列更加灵活。

总结：总的来说，在可以确定队列长度的最大值的情况下，建议用循环队列，如果你无法估计队列的长度，那就用链式队列。

五、优先级队列：

　　优先级队列是带有优先级的队列。

　　　　用顺序存储结构实现的优先级队列称作顺序优先级队列。

　　　　用链式存储结构存储的优先级队列称作链式优先级队列。

顺序优先级队列和顺序循环队列相比主要有两点不同：

（1）对于顺序优先级队列来说，出队列操作不是把队头数据元素出队列，而是把队列中优先级最高的数据元素出队列。（入队操作没区别）

（2）对于顺序优先级队列来说，数据元素由两部分组成，一部分是原先意义上的数据元素，另一部分是优先级。通常设计优先级为int类型的数值，并规定数值越小优先级越高。

1、顺序优先队列的实现：

设计顺序优先级队列分为两个类：

　　数据元素类

　　优先级队列类

代码实现：

(1)Element.java:

1 //优先级队列元素类 2 public class Element { 3 4 private Object element; // 数据 5 private int priority; // 优先级 6 7 public Element(Object obj, int priority) { 8 this.element = obj; 9 this.priority = priority; 10 } 11 12 public Object getElement() { 13 return element; 14 } 15 16 public void setElement(Object element) { 17 this.element = element; 18 } 19 20 public int getPriority() { 21 return priority; 22 } 23 24 public void setPriority(int priority) { 25 this.priority = priority; 26 } 27 28 }

(2)Queue.java:

(3)PrioritySequenceQueue.java:

1 //优先级队列 2 public class PrioritySequenceQueue implements Queue { 3 4 static final int defaultSize = 10; //默认队列长度 5 int front; //队头 6 int rear; //队尾 7 int count; //计数器 8 int maxSize; //队列最大长度 9 Element[] queue; //队列 10 11 public PrioritySequenceQueue() { 12 init(defaultSize); 13 } 14 15 public PrioritySequenceQueue(int size) { 16 init(size); 17 } 18 19 public void init(int size) { 20 maxSize = size; 21 front = rear = 0; 22 count = 0; 23 queue = new Element[size]; 24 } 25 26 @Override 27 public void append(Object obj) throws Exception { 28 // TODO Auto-generated method stub 29 //如果队列已满 30 if (count >= maxSize) { 31 throw new Exception("队列已满！"); 32 } 33 queue[rear] = (Element) obj; 34 rear++; 35 count++; 36 } 37 38 @Override 39 public Object delete() throws Exception { 40 // TODO Auto-generated method stub 41 if (isEmpty()) { 42 throw new Exception("队列为空！"); 43 } 44 //默认第一个元素为优先级最高的。 45 Element min = queue[0]; 46 int minIndex = 0; 47 for (int i = 0; i < count; i++) { 48 if (queue[i].getPriority()

【本文地址】

数据结构Java实现07

数据结构Java实现07

今日新闻

推荐新闻